/* 二叉树先序遍历 */
const tree = {
  val: "a",
  left: {
    val: "b",
    left: {
      val: "e",
      left: null,
      right: null,
    },
    right: {
      val: "f",
      left: null,
      right: null,
    },
  },
  right: {
    val: "c",
    left: {
      val: "g",
      left: null,
      right: null,
    },
    right: {
      val: "h",
      left: null,
      right: null,
    },
  },
};

/* 递归版 */
/* const preOrder = (root) => {
  if (!root) return;
  console.log(root.val);
  preOrder(root.left);
  preOrder(root.right);
}; */

/* 非递归版 */

const preOrder = (root) => {
  const stack = [root];

  while (stack.length) {
    const n = stack.pop(); // 栈顶出
    console.log(n.val);
    /* 下面两行两者顺序注意, 栈是先进后出 */
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
};
preOrder(tree);
